package com.github.yangyishe.p100;

import com.github.yangyishe.ListNode;

/**
 * 23. 合并 K 个升序链表
 * https://leetcode.cn/problems/merge-k-sorted-lists/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 *
 *
 * 示例 1：
 *
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下：
 * [
 *   1->4->5,
 *   1->3->4,
 *   2->6
 * ]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 * 示例 2：
 *
 * 输入：lists = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：lists = [[]]
 * 输出：[]
 *
 *
 * 提示：
 *
 * k == lists.length
 * 0 <= k <= 10^4
 * 0 <= lists[i].length <= 500
 * -10^4 <= lists[i][j] <= 10^4
 * lists[i] 按 升序 排列
 * lists[i].length 的总和不超过 10^4
 */
public class Problem23 {
    public static void main(String[] args) {
        int[][] nums=new int[][]{
                {1,4,5},{1,3,4},{2,6}
        };
        ListNode[] nodes=new ListNode[nums.length];
        for(int i=0;i<nums.length;i++){
            nodes[i]=ListNode.getInstance(nums[i]);
        }

        Problem23 problem23 = new Problem23();
        ListNode node = problem23.mergeKLists(nodes);
        node.print();

    }

    /**
     * 思路:
     * 分治.
     * 先合并前两个, 得到一个新的链表;
     * 再合并新链表和其后的一个.
     * 一直到最后
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode temp=null;
        for (ListNode listNode : lists) {
            temp=mergeTwo(temp,listNode);
        }
        return temp;
    }

    public ListNode mergeTwo(ListNode node1,ListNode node2){
        ListNode temp1=node1;
        ListNode temp2=node2;
        ListNode result=new ListNode();
        ListNode resultTemp=result;
        while(temp1!=null||temp2!=null){
            if(temp1==null){
                resultTemp.next=temp2;
                break;
            }else if(temp2==null){
                resultTemp.next=temp1;
                break;
            }else{
                if(temp1.val<temp2.val){
                    resultTemp.next=new ListNode(temp1.val);
                    temp1=temp1.next;
                }else{
                    resultTemp.next=new ListNode(temp2.val);
                    temp2=temp2.next;
                }
                resultTemp=resultTemp.next;
            }
        }

        return result.next;
    }
}
